package com.company;



import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入中序：");
        //HDIBEMJNAFCKGL
        String inOrder = scanner.nextLine();
        System.out.println("输入先序：");
        //ABDHIEJMNCFGKL
        String preOrder = scanner.nextLine();

        char[] in = inOrder.toCharArray();
        char[] pre = preOrder.toCharArray();
//        System.out.println(pre[0]);

        LinkedBinaryTree tree = returnTree(in,pre);
        System.out.println(tree.toString());



    }

    public static LinkedBinaryTree returnTree(char[] in, char[] pre)
    {
        LinkedBinaryTree tree;
        if(pre.length == 0 || in.length == 0 || pre.length != in.length){
            tree =  new LinkedBinaryTree();
        }
        else {
            int x = 0;
            while (in[x] != pre[0]) {
                x++;
            }

            char[] inLeft = new char[x];
            char[] preLeft = new char[x];
            char[] inRight = new char[in.length - x - 1];
            char[] preRight = new char[pre.length - x - 1];

            for (int y = 0; y < in.length; y++) {
                if (y < x) {
                    inLeft[y] = in[y];
                    preLeft[y] = pre[y + 1];
                } else if (y > x) {
                    inRight[y - x - 1] = in[y];
                    preRight[y - x - 1] = pre[y];
                }
            }
            LinkedBinaryTree left = returnTree(inLeft, preLeft);
            LinkedBinaryTree right = returnTree(inRight, preRight);
            tree = new LinkedBinaryTree(pre[0], left,right);
        }
        return tree;
    }
}
